Field of the Invention
The present invention relates to an auto-optimizing out-of-core method and system for rendering of large engineering three-dimensional (3D) Computer Aided Design (CAD) assemblies on low-memory handheld devices, wherein the CAD assemblies comprise of a plurality of parts containing triangulated geometry data, and wherein the total size of the part triangulated geometry data exceeds the available random access memory (RAM).
Description of the Related Art
Designers using 3D CAD applications can prototype engineering components and structures much faster because they can visualize and modify the model in 3D and from multiple points of view. 3D CAD additionally enables designers and engineers to test the strength, performance and manufacturability of their designs. This can be done by simulating the response to anticipated forces, animating the interaction between different components, simulating manufacturing process, and performing various other types of analysis on the 3D CAD models. The ability to perform these tests on a digital prototype significantly decreases the time required to design a complex product.
Complex engineering components like the engines, supporting structures and other parts of automobiles, aircrafts and other machinery cannot usually be designed as a single entity. These complex engineering models are therefore modeled as several smaller individual parts, often by big teams of engineers and designers. The individually designed components are then assembled into another CAD design known as a CAD assembly. A CAD assembly can frequently comprise of hundreds if not thousands of parts. When assembled together designers can visualize how the individual parts fit together and interact with each other. Designers and engineers can also perform additional and more complex simulations and analysis on a CAD assembly. For example, they can test if the individual parts will fit properly and if they will work together in practice.
Essential to all these activities is the ability to visualize CAD parts and assemblies in 3D on digital screens and monitors. Usually most engineering CAD models are designed using continuous parametric surfaces and solids. However, for the purpose of viewing them in 3D these parametric surfaces need to be triangulated into a set of discrete triangles. This is because popular 3D programming application-programming-interfaces (APIs) like OpenGL expect the input data to be in a triangulated form for performance reasons. Triangulation methods approximate a parametric surface by a connected set of triangles within some given tolerance. The smaller the tolerance the greater the number of triangles that are required to approximate the surface.
3D CAD applications usually store the CAD geometry data to disk in their native parametric format. However, there are also several formats, like STL and OBJ, which store the geometry data in a triangulated format suitable for rendering in 3D. Additionally, there are several open source and commercial libraries which can triangulate parametric 3D CAD data. For the purposes of the current invention we will assume that the CAD geometry data is already available in a triangulated format.
For rendering in 3D the triangulated geometry data of a part is preferably first copied from the storage device into the random access memory. This is because reading and rendering data from the random-access-memory is an order of magnitude faster than reading data from a storage device like a hard disk. It is therefore preferable to load all the triangulated geometry data in memory before rendering.
There are however cases in which the size of the triangulated geometry data comprising a 3D CAD assembly can be larger than the size of the available memory. In these situations a portion of the triangulated geometry data can be read directly from disk and then rendered. Such rendering methods are known as out-of-core rendering methods, where out-of-core means outside of random access memory. Because these methods read a portion of the triangulated geometry data from disk, out-of-core rendering methods tend to be much slower. To mitigate this drop in performance, out-of-core rendering methods are clubbed with various optimization techniques.
Handheld mobile devices, like smartphones and tablets, are growing in popularity. Designers and engineers frequently need to share 3D CAD models for review with each other and sales people often need to showcase 3D CAD models to customers and partners. The ability to visualize 3D CAD models on the go on handheld mobile devices can therefore enhance collaboration, thus enabling rapid product development and sales.
Because handheld devices are very compact and lightweight, they currently have limited random access memory and processing power due to space and battery constraints. The total size of the triangulated geometry data comprising a large 3D CAD assembly can therefore often exceed the size of the available RAM in a handheld device. A trivial rendering method that loads the complete triangulated geometry data from disk into the RAM therefore won't be able to render the complete CAD assembly on such devices.
Mesh simplification is a technique where the triangulated data is simplified or reduced by combining or collapsing multiple connected triangles into a single larger triangle. However, the lesser the number of triangles used to approximate a parametric surface the lower the accuracy of representation. When a mesh simplification technique combines multiple triangles into a single triangle, it does reduce the size of the triangulated geometry data but at the cost of reduced accuracy. (See: Kok-Lim Low, Tiow-Seng Tan. Model Simplification Using Vertex Clustering. Proceedings of the 1997 symposium on Interactive 3D graphics, 1997). Mesh simplification, beyond a certain extent, can also result in significant loss of geometric detail.
There are some runtime techniques which can also reduce the amount of triangulated data that needs to be stored in memory. Frustum culling is a technique where the data outside the user's viewport is filtered out and not rendered. Occlusion culling is another technique where a geometry that is hidden by another geometry from the current point of view is not rendered. While these techniques are primarily used to improve the rendering performance, they can also reduce the amount of triangulated geometry data that needs to be loaded at a time into the random access memory (See: T. Hudson, D. Manocha, J. Cohen, M. Lin, K. Hoff, and H. Zhang. Accelerated occlusion culling using shadow frusta. SCG '97 Proceedings of the thirteenth annual symposium on Computational geometry, 1997). Because these techniques need to be applied at runtime during the rendering process, they can be computationally too intensive for a handheld device. These techniques therefore has the potential to slow down the rendering on a hand-held device instead of making it faster.
Out-of-core methods can be used to process large data when there is limited available memory (See: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data. ACM Computing Surveys (CSUR) Volume 33 Issue 2, June 2001 Pages 209-271). There are several out-of-core rendering techniques focused on interactive rendering, and they often use a combination of filtering and simplification techniques to reduce the triangulated geometry data (See: W. T. Correa, J. T. Klosowski, and C. T. Silva. iWalk: Interactive Out-Of-Core Rendering of Large Models. Technical Report TR-653-02, Princeton University, 2002).
Many of the parts comprising a typical engineering 3D CAD assembly are however visible from many points of view. This decreases the effectiveness of filtering techniques which are more useful while rendering architectural and other large scale models. Moreover filtering techniques are useful when the rending point of view is located within the model or a scene where the field of view is narrow and where the scene is projected in perspective. In the case engineering CAD models however the point of view is almost always outside the model and the scene is usually rendered in an orthographic projection. Engineering 3D CAD models also require precise visualization, and therefore model simplification, beyond a certain level, is undesirable. Filtering and simplification techniques also require extensive pre-processing and runtime computations. This can slow down both the loading of the file and the rendering on a handheld device.
A trivial implementation of an out-of-core rendering technique, where a portion of the triangulated geometry data is rendered from memory and the rest directly from a storage device, may be too slow for large CAD assemblies. This is because accessing data directly from the disk during rendering can be extremely slow. It is possible to increase the efficiency of such a system by using a part of the memory to cache the triangulated geometry data that would otherwise be read directly from disk. This cache can be updated by a concurrently running process which can remove rendered parts from the cache and load the triangulated geometry data for the yet to be rendered parts into the cache. The rendering process can then render most of the parts from the cache instead of the storage device, thus improving the rendering speed. It is however difficult to determine an optimum size for such a cache (See: Gannon, Dennis, William Jalby, and Kyle Gallivan. “Strategies for cache and local memory management by global program transformation.” Journal of parallel and distributed computing 5.5 (1988): 587-616).